#include"sorting.h"
#include"makevector.h"
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<ctime>
#include <vector>
using namespace std;
/**
 * @brief 设置了几个常量a,b,c,d用于代表数组的有序度
 * 有序数组的生成通过前N%的数组元素为以0为首的自然数序列
 * 其后的数组元素为随机数组，将两个数组合并，这样就生成了
 * 一定有序度的数组用于测试，注意测试中间，要用深度复制的
 * 原数组，这样保证第二次排序测试不会用一个已经完全排序的数组。
 * 
 * @return int 
 */
int main()
{   
    const float a=0.01;
    const float b=0.1;
    const float c=0.9;
    const float d=0.99;
    const int e=1;
    int N ;
    cin >> N;

    vector<int> laneLabel1(N*a),laneLabel2(N*b),laneLabel3(N*c),laneLabel4(N*d), roadLabel, vector1,vector2,vector3,vector4;
    create_rand obj;
    /**
     * @brief vector1,2,3,4分别是有序度0.01，0.10，0.90，0.99的向量
     * 
     */

  /*  roadLabel  = obj.create_rand_int_number_include_a(N*a, 10000000, N*(e-a));
    for (int i = 0; i < (N*a) ; ++i)
	{
		laneLabel1[i] = i;
	}
    vector1.insert(vector1.end(), laneLabel1.begin(), laneLabel1.end());
    vector1.insert(vector1.end(), roadLabel.begin(), roadLabel.end());
*/
    roadLabel  = obj.create_rand_int_number_include_a(N*b, 10000000, N*(e-b));
    for (int i = 0; i < (N*b) ; ++i)
	{
		laneLabel2[i] = i;
	}
	vector2.insert(vector1.end(), laneLabel2.begin(), laneLabel2.end());
    vector2.insert(vector1.end(), roadLabel.begin(), roadLabel.end());
    vector<int> vector2b=vector2;
/*
    roadLabel  = obj.create_rand_int_number_include_a(N*c, 10000000, N*(e-c));
    for (int i = 0; i < (N*c) ; ++i)
	{
		laneLabel3[i] = i;
	}
	vector3.insert(vector1.end(), laneLabel3.begin(), laneLabel3.end());
    vector3.insert(vector1.end(), roadLabel.begin(), roadLabel.end());
*/
    /**roadLabel  = obj.create_rand_int_number_include_a(N*d, 10000000, N*(e-d));
    for (int i = 0; i < (N*d) ; ++i)
	{
		laneLabel4[i] = i;
	}
	vector4.insert(vector1.end(), laneLabel4.begin(), laneLabel4.end());
    vector4.insert(vector1.end(), roadLabel.begin(), roadLabel.end());
*/
    clock_t startTime1 =clock();
	heapsort(vector2);
	clock_t endTime1 = clock();
    cout << "heapsort sorting time :" << double(endTime1 - startTime1)/ CLOCKS_PER_SEC << "s" << endl;
        
    clock_t startTime2 =clock();
	quicksort(vector2b);
	clock_t endTime2 = clock();
    cout << "quicksort sorting time :" << double(endTime2 - startTime2)/ CLOCKS_PER_SEC << "s" << endl;
	
    return 0;
};